﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.Problems.ShortestPaths.Acyclic
{
    public class MemoizedDagShortestPathsFinder<T> : IMinimumDistanceFinder<T,double>
    {
        private readonly Func<IEnumerable<T>, IMap<T, double>> _createMap;

        public MemoizedDagShortestPathsFinder(Func<IEnumerable<T>,IMap<T,double>> createMap = null)
        {
            _createMap = createMap ?? (it => AlgoritmiaFactory.Maps<T, double>.Default);
        }


        #region IMinimumDistanceFinder<T,double>

        public double SomeToSomeDistance(IDigraph<T> g, WeightingFunction<T, double> d, IEnumerable<T> sources, IEnumerable<T> targets)
        {
            var memory = _createMap(g.V);
            var sourcesList = sources.ToList();

            Func<T, double> D = null;
            D = v =>
                    {
                        foreach (var p in g.Predecessors(v))
                        {
                            if (!memory.Contains(p))
                            {
                                memory[p] = D(p);
                            }
                        }
                        double result = (from p in g.Predecessors(v)
                                         select memory[p] + d(p, v)).DefaultIfEmpty(double.PositiveInfinity).Min();
                        return sourcesList.Contains(v) ? Math.Min(0, result) : result;
                    };

            foreach(var t in targets)
            {
                if (!memory.Contains(t))
                {
                    memory[t] = D(t);
                }
            }
            return (from t in targets
                    select memory[t]).Min();
        }

        #endregion
    }
}
